package Search;

import java.util.ArrayList;
import java.util.List;

//插值查找
public class InsertValueSearch {
	public static void main(String[] args) {
		//初始化一个连续数组
//        int[] array = new int[100];
//        for (int i = 0; i < 100; i++){
//            array[i] = i+1;
//        }
		int[] array = {4};
		System.out.println(insertValueSearch(array, 0, array.length - 1, 1));
	}

	public static List<Integer> insertValueSearch(int[] array, int left, int right, int findVal) {
		List<Integer> result = new ArrayList<>();

		//大于最大的数，小于最小的数，退出
		if (left > right || findVal < array[0] || findVal > array[array.length - 1]) {
			return result;
		}

		//插值排序，自适应的 mid ，提高查找效率
		int mid = left + (right - left) * (findVal - array[left]) / (array[right] - array[left]);
		int midVal = array[mid];

		if (findVal > midVal) {
			//向右边递归
			return insertValueSearch(array, mid + 1, right, findVal);
		} else if (findVal < midVal) {
			//向左边递归
			return insertValueSearch(array, left, mid - 1, findVal);
		} else {
			int m = mid;
			while (m - 1 >= 0 && array[m - 1] == findVal) {
				m--;
				result.add(m);
			}

			result.add(mid);

			m = mid;
			while (m + 1 <= array.length - 1 && array[m + 1] == findVal) {
				m++;
				result.add(m);
			}
			return result;
		}
	}
}
